/*
 * 线性表-链式存储结构
 * 参考大话数据结构和Weiss "DSAAC"
 *
 */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/* type */
struct Student {
    int id;
    char name[100];
    int age;
    char sex;
};
typedef struct Student ElemType;
//typedef int ElemType;


/*
 * 单链表
 */
struct node {
    ElemType data;
    struct node *next;
};
typedef struct node list_t;
typedef struct node *LinkList;


/*
 * 双向链表
 */
struct dnode {
    ElemType data;
    struct dnode *next;   /* 直接后继指针 */
    struct dnode *prior;  /* 直接前驱指针 */
};
typedef struct dnode double_list_t;


struct my_node {
    void *data;
    struct my_node *next;
};
typedef struct my_node  mylist_t;



/* 不带头结点 */
void init_link_list(list_t **list);
int  get_link_list_length(list_t *list);
int  insert_link_list(list_t **list, int pos, ElemType *item);
int  insert_link_list_aft(list_t **list, int pos, ElemType *item);
int  insert_link_list_bfe(list_t **list, int pos, ElemType *item);
int  insert_link_list_head(list_t **list, ElemType *item);
int  insert_link_list_tail(list_t **list, ElemType *item);
int  delete_link_list_item(list_t **list, int pos, ElemType *item);
int  get_link_list_item(list_t *list, int pos, ElemType *item);
int  find_link_list_item(list_t *list, ElemType *item);
void trave_link_list(list_t *list, void (*print_info)(int n, ElemType *item));
void free_link_list(list_t **list);


/* 带头结点 */
int  init_list(list_t **list);
int  is_list_empty(list_t *list);
int  get_list_length(list_t *list);
int  insert_list(list_t **list, int pos, ElemType *item);
int  insert_list_head(list_t **list, ElemType *item);
int  insert_list_tail(list_t **list, ElemType *item);
int  delete_list_item(list_t **list, int pos, ElemType *item);
int  get_list_item(list_t *list, int pos, ElemType *item);
int  find_list_item(list_t *list, ElemType *item);
void trave_list(list_t *list, void (*print_info)(int n, ElemType *item));
void free_list(list_t **list);


int  Insert_LinkList(LinkList *list, int pos, ElemType *item);


/*

带头结点单链表

        +---+-+   +----+-+   +----+-+           +----+------+
 head-->| ^ | +-->| a1 | +-->| a2 | +--> ... -->| an | NULL |
        +---+-+   +----+-+   +----+-+           +----+------+


不带头结点单链表(只有头结点)
        +----+-+   +----+-+           +----+------+
 head-->| a1 | +-->| a2 | +--> ... -->| an | NULL |
        +----+-+   +----+-+           +----+------+

不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息，它是为了方便做的一种处理。

为什么要设置头结点？
1、处理起来方便。例如，对在第一元素结点前插入结点和删除第一结点操作与其他结点的操作就统一了。
2、无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

*/


void
print_student_info(int n, ElemType *stu)
{
    printf("No[%d]: Stu_id[%d], Stu_Name[%s]\n", n, stu->id, stu->name);
}



/* 不带头结点的操作 */
void fun_1()
{
    int i;
    int n;
    list_t *list; /* 头指针 */

    /* 初始化不带头结点的单链表，可以直接 list = NULL; */
    /* 注意要把指针的地址传给函数，否则函数修改不了头指针的指向 */
    init_link_list(&list);

    ElemType item;

    /* 插入10个节点 */
    for (i = 0; i < 10; ++i) {
        memset(&item, 0, sizeof(item));
        item.id = i+1;
        snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
        insert_link_list(&list, i+1, &item);
    }

    /* 在第5个位置插入一个节点 (新插入节点排在第5位) */
    memset(&item, 0, sizeof(item));
    item.id = 11;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_link_list(&list, 5, &item);

    /* 在最后1个位置后插入一个节点 (新插入节点排在第12位) */
    n = get_link_list_length(list);
    memset(&item, 0, sizeof(item));
    item.id = 12;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_link_list(&list, n+1, &item);


    memset(&item, 0, sizeof(item));
    item.id = 20;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    printf("insert at pos 20, ret[%d]\n", insert_link_list(&list, 20, &item));
    printf("insert at pos -1, ret[%d]\n", insert_link_list(&list, -1, &item));


    printf("\n");
    n = get_link_list_length(list);
    printf("After insert: n=[%d]\n", n);
    for (i = 0; i < n; ++i) {
        memset(&item, 0, sizeof(item));
        get_link_list_item(list, i+1, &item); /* 应该要实现一个遍历链表的函数，而不是调用获取指定位置元素的函数 */
        printf("No[%d]: Stu_id[%d], Stu_Name[%s]\n", i+1, item.id, item.name);
    }

    /* 头插法 */
    memset(&item, 0, sizeof(item));
    item.id = 13;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_link_list_head(&list, &item);

    memset(&item, 0, sizeof(item));
    item.id = 14;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_link_list_head(&list, &item);

    /* 尾插法 */
    memset(&item, 0, sizeof(item));
    item.id = 15;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_link_list_tail(&list, &item);

    memset(&item, 0, sizeof(item));
    item.id = 16;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_link_list_tail(&list, &item);


    printf("\n");
    n = get_link_list_length(list);
    printf("After insert: n=[%d]\n", n);
    trave_link_list(list, print_student_info);


    printf("\n");
    /* 删除第一个元素 */
    delete_link_list_item(&list, 1, NULL);

    /* 删除最后一个元素 */
    n = get_link_list_length(list);
    delete_link_list_item(&list, n, NULL);

    /* 删除第3个元素 */
    memset(&item, 0, sizeof(item));
    delete_link_list_item(&list, 3, &item);
    printf("删除第3个元素: Stu_id[%d], Stu_Name[%s]\n", item.id, item.name);

    /* 删除第一个元素 */
    delete_link_list_item(&list, 1, NULL);

    /* 删除最后一个元素 */
    n = get_link_list_length(list);
    delete_link_list_item(&list, n, NULL);

    printf("\n");
    n = get_link_list_length(list);
    printf("After insert: n=[%d]\n", n);
    trave_link_list(list, print_student_info);


    /* 查找元素， 对比函数应该也是使用回调函数才正确，由使用者传入 */
    printf("\n");
    memset(&item, 0, sizeof(item));
    item.id = 7;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    if (n = find_link_list_item(list, &item))
        printf("元素[%d]能找到, pos[%d]\n", item.id, n);
    else
        printf("元素[%d]不能找到\n", item.id);

    memset(&item, 0, sizeof(item));
    item.id = 20;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    if (n = find_link_list_item(list, &item))
        printf("元素[%d]能找到, pos[%d]\n", item.id, n);
    else
        printf("元素[%d]不能找到\n", item.id);


    printf("删除链表前，元素个数[%d]\n", get_link_list_length(list));
    free_link_list(&list);
    free_link_list(&list);
    printf("删除链表后，元素个数[%d]\n", get_link_list_length(list));


    memset(&item, 0, sizeof(item));
    item.id = 20;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    printf("insert at pos 20, ret[%d]\n", insert_link_list(&list, 20, &item));
    printf("insert at pos -1, ret[%d]\n", insert_link_list(&list, -1, &item));


    printf("\n");

    /* 空链表插入第一个节点 */
    memset(&item, 0, sizeof(item));
    item.id = 1;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_link_list(&list, 1, &item);

    /* 在第1个位置插入一个节点 (新插入节点排在第1位) */
    memset(&item, 0, sizeof(item));
    item.id = 2;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_link_list(&list, 1, &item);

    /* 在第1个位置后插入一个节点 (新插入节点排在第1位) */
    memset(&item, 0, sizeof(item));
    item.id = 3;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_link_list(&list, 1, &item);

    /* 在第2个位置插入一个节点 (新插入节点排在第2位) */
    memset(&item, 0, sizeof(item));
    item.id = 4;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_link_list(&list, 2, &item);

    printf("\n");
    n = get_link_list_length(list);
    printf("After insert: n=[%d]\n", n);
    trave_link_list(list, print_student_info);

    printf("删除链表前，元素个数[%d]\n", get_link_list_length(list));
    free_link_list(&list);
    printf("删除链表后，元素个数[%d]\n", get_link_list_length(list));
}


/* 带头结点的操作 */
void fun_2()
{
    int i;
    int n;
    list_t *list; /* 头指针 */


    /* 初始化带头结点的单链表，可以直接
    list_t header;
    memset(&header, 0, sizeof(header));
    header.next = NULL;
    list = &header;
    */
    /* 注意要把指针的地址传给函数，否则函数修改不了头指针的指向 */
    init_list(&list);

    ElemType item;

    /* 插入10个节点 */
    for (i = 0; i < 10; ++i) {
        memset(&item, 0, sizeof(item));
        item.id = i+1;
        snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
        insert_list(&list, i+1, &item);
    }

    /* 在第5个位置插入一个节点 (新插入节点排在第5位) */
    memset(&item, 0, sizeof(item));
    item.id = 11;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_list(&list, 5, &item);

    /* 在最后1个位置后插入一个节点 (新插入节点排在第12位) */
    memset(&item, 0, sizeof(item));
    item.id = 12;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    n = get_list_length(list);
    insert_list(&list, n+1, &item);


    memset(&item, 0, sizeof(item));
    item.id = 20;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    printf("insert at pos 20, ret[%d]\n", insert_list(&list, 20, &item));
    printf("insert at pos -1, ret[%d]\n", insert_list(&list, -1, &item));


    printf("\n");
    n = get_list_length(list);
    printf("After insert: n=[%d]\n", n);
    for (i = 0; i < n; ++i) {
        memset(&item, 0, sizeof(item));
        get_list_item(list, i+1, &item); /* 应该要实现一个遍历链表的函数，而不是调用获取指定位置元素的函数 */
        printf("No[%d]: Stu_id[%d], Stu_Name[%s]\n", i+1, item.id, item.name);
    }

    /* 头插法 */
    memset(&item, 0, sizeof(item));
    item.id = 13;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_list_head(&list, &item);

    memset(&item, 0, sizeof(item));
    item.id = 14;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_list_head(&list, &item);

    /* 尾插法 */
    memset(&item, 0, sizeof(item));
    item.id = 15;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_list_tail(&list, &item);

    memset(&item, 0, sizeof(item));
    item.id = 16;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_list_tail(&list, &item);


    printf("\n");
    n = get_list_length(list);
    printf("After insert: n=[%d]\n", n);
    trave_list(list, print_student_info);


    printf("\n");
    /* 删除第一个元素 */
    delete_list_item(&list, 1, NULL);

    /* 删除最后一个元素 */
    n = get_list_length(list);
    delete_list_item(&list, n, NULL);

    /* 删除第3个元素 */
    memset(&item, 0, sizeof(item));
    delete_list_item(&list, 3, &item);
    printf("删除第3个元素: Stu_id[%d], Stu_Name[%s]\n", item.id, item.name);

    /* 删除第一个元素 */
    delete_list_item(&list, 1, NULL);

    /* 删除最后一个元素 */
    n = get_list_length(list);
    delete_list_item(&list, n, NULL);

    printf("\n");
    n = get_list_length(list);
    printf("After insert: n=[%d]\n", n);
    trave_list(list, print_student_info);


    /* 查找元素， 对比函数应该也是使用回调函数才正确，由使用者传入 */
    printf("\n");
    memset(&item, 0, sizeof(item));
    item.id = 7;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    if (n = find_list_item(list, &item))
        printf("元素[%d]能找到, pos[%d]\n", item.id, n);
    else
        printf("元素[%d]不能找到\n", item.id);

    memset(&item, 0, sizeof(item));
    item.id = 20;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    if (n = find_list_item(list, &item))
        printf("元素[%d]能找到, pos[%d]\n", item.id, n);
    else
        printf("元素[%d]不能找到\n", item.id);


    printf("删除链表前，元素个数[%d]\n", get_list_length(list));
    free_list(&list);
    free_list(&list);
    printf("删除链表后，元素个数[%d]\n", get_list_length(list));


    memset(&item, 0, sizeof(item));
    item.id = 20;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    printf("insert at pos 20, ret[%d]\n", insert_list(&list, 20, &item));
    printf("insert at pos -1, ret[%d]\n", insert_list(&list, -1, &item));


    /* 空链表插入第一个节点 */
    memset(&item, 0, sizeof(item));
    item.id = 1;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_list(&list, 1, &item);

    /* 在第1个位置插入一个节点 (新插入节点排在第1位) */
    memset(&item, 0, sizeof(item));
    item.id = 2;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_list(&list, 1, &item);

    /* 在第1个位置插入一个节点 (新插入节点排在第1位) */
    memset(&item, 0, sizeof(item));
    item.id = 3;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    insert_list(&list, 1, &item);

    /* 在第2个位置插入一个节点 (新插入节点排在第2位) */
    memset(&item, 0, sizeof(item));
    item.id = 4;
    snprintf(item.name, sizeof(item.name), "Stu_%02d", item.id);
    Insert_LinkList(&list, 2, &item);


    printf("\n");
    n = get_list_length(list);
    printf("After insert: n=[%d]\n", n);
    trave_list(list, print_student_info);

    printf("删除链表前，元素个数[%d]\n", get_list_length(list));
    free_list(&list);
    printf("删除链表后，元素个数[%d]\n", get_list_length(list));
}

int
main(int argc, char *argv[])
{

    fun_1();

    return 0;

}



/******************************************************************************/

/*
 * 初始化不带头结点的单链表
 *
 * 注意这里是指向指针的指针，因为我们要修改头指针的指向
 */
void
init_link_list(list_t **list)
{
    *list = NULL; /* 置单链表为空 */
}

/*
 * 返回不带头结点的单链表节点个数
 *
 * 时间复杂度为 O(n)
 * 如果有个变量跟踪节点个数，则时间复杂度为O(1)
 */
int
get_link_list_length(list_t *list)
{
    int i;
    list_t *ptr;

    ptr = list;

    i = 0;
    while (ptr) {
        ptr = ptr->next;
        ++i;
    }

    return i;
}



/*
 * 不带头结点单链表插入，如果是空链表，插入第1个节点，否则在第 n 个位置插入新节点
 *
 * pos的范围是 [1, length+1]
 * 成功返回0
 *
 * 时间复杂度为 O(n)
 */
int
insert_link_list(list_t **list, int pos, ElemType *item)
{
    int i;
    list_t *ptr;
    list_t *newptr;

    ptr = *list;

    i = 2;
    if (pos != 1) {
        while (ptr && i < pos) {
            ptr = ptr->next;
            ++i;
        }
        if (ptr == NULL || i > pos)
            return -1;
    }

    newptr = malloc(sizeof(list_t));
    if (newptr == NULL)
        return -2;

    memcpy(&newptr->data, item, sizeof(ElemType));
    if (ptr == NULL || pos == 1) { /* 插入第一个节点 */
        newptr->next = ptr;
        *list = newptr;
    } else {
        newptr->next = ptr->next;
        ptr->next = newptr;
    }

    return 0;



}

/*
 * 废弃
 *
 * 不带头结点单链表插入，如果是空链表，插入第1个节点，否则在第 n 个数据后插入新节点
 *
 * 单链表第 n 个数据插入结点的算法思路:
 * 1. 声明一结点 p 指向链表第一个结点，初始化 i 从 1 开始
 * 2. 当 i<n 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，i 累加 1;
 * 3. 若到链表末尾 p 为空，则说明第 n 个元素不存在
 * 4. 否则查找成功，在系统中生成一个空结点 s;
 * 5. 将数据元素 e 赋值给 s->data ;
 * 6. 单链表的插入标准语句 s->next=p->next, p->next=s ;
 * 7. 返回成功。
 *
 * pos的范围是 [1, length]
 * 成功返回0
 *
 * 时间复杂度为 O(n)
 */
int
insert_link_list_aft(list_t **list, int pos, ElemType *item)
{
    int i;
    list_t *ptr;
    list_t *newptr;

    ptr = *list;

    i = 1;
    if (ptr != NULL) {
        while (ptr && i < pos) {
            ptr = ptr->next;
            ++i;
        }
        if (ptr == NULL || i > pos)
            return -1;
    }

    newptr = malloc(sizeof(list_t));
    if (newptr == NULL)
        return -2;

    memcpy(&newptr->data, item, sizeof(ElemType));
    if (ptr == NULL) { /* 空链表插入第一个节点 */
        newptr->next = NULL;
        *list = newptr;
    } else {
        newptr->next = ptr->next;
        ptr->next = newptr;
    }

    return 0;
}

/*
 * 废弃
 *
 * 不带头结点单链表插入，如果是空链表，插入第1个节点，否则在第 i 个数据前插入新节点 (在第i个位置插入节点)
 *
 * pos的范围是 [1, length]
 * 成功返回0
 *
 * 时间复杂度为 O(n)
 */
int
insert_link_list_bfe(list_t **list, int pos, ElemType *item)
{
    int i;
    list_t *ptr;
    list_t *newptr;

    ptr = *list;

    i = 2;
    if (ptr != NULL || pos != 1) {
        while (ptr && i < pos) {
            ptr = ptr->next;
            ++i;
        }
        if (ptr->next == NULL || i > pos)
            return -1;
    }

    newptr = malloc(sizeof(list_t));
    if (newptr == NULL)
        return -2;

    memcpy(&newptr->data, item, sizeof(ElemType));
    if (ptr == NULL || pos == 1) { /* 插入第一个节点 */
        newptr->next = ptr;
        *list = newptr;
    } else {
        newptr->next = ptr->next;
        ptr->next = newptr;
    }

    return 0;
}




/*
 * 不带头结点单链表插入 - 头插法
 *
 * 时间复杂度为 O(1)
 */
int
insert_link_list_head(list_t **list, ElemType *item)
{
    list_t *ptr;
    list_t *newptr;

    ptr = *list;

    newptr = malloc(sizeof(list_t));
    if (newptr == NULL)
        return -1;
    memcpy(&newptr->data, item, sizeof(ElemType));

    newptr->next = ptr;
    *list = newptr;

    return 0;
}

/*
 * 不带头结点单链表插入 - 尾插法
 *
 * 时间复杂度为 O(n)
 * 如果有指向结尾的指针，则时间复杂度为 O(1)
 */
int
insert_link_list_tail(list_t **list, ElemType *item)
{
    list_t *ptr;
    list_t *newptr;

    ptr = *list;

    /* point to the tail */
    if (ptr != NULL) {
        while (ptr->next)
            ptr = ptr->next;
    }

    newptr = malloc(sizeof(list_t));
    if (newptr == NULL)
        return -1;
    memcpy(&newptr->data, item, sizeof(ElemType));

    if (ptr == NULL) {
        newptr->next = NULL;
        *list = newptr;
    } else {
        newptr->next = NULL;
        ptr->next = newptr;
    }

    return 0;
}



/*
 * 不带头结点单链表删除
 *
 * 单链表第 i 个数据删除结点的算法思路:
 * 1.声明一结点 p 指向链表第一个结点， 初始化 j 从1 开始
 * 2.当 j<i 时，就遍历链表， 让 p 的指针向后移动，不断指向下一个结点，j 累加 1
 * 3.若到链表末尾 p 为空，则说明第 i 个元素不存在;
 * 4.否则查找成功，将欲删除的结点 p->next 赋值给q;
 * 5.单链表的删除标准语句 p->next=q->next;
 * 6.将 q 结点中的数据赋值给 e ，作为返回;
 * 7.释放 q 结点;
 * 8.返回成功。
 *
 * pos的范围是 [1, length]
 * 成功返回0
 *
 * 时间复杂度为 O(n)
 */
int
delete_link_list_item(list_t **list, int pos, ElemType *item)
{
    int i;
    list_t *ptr;
    list_t *nextptr;

    ptr = *list;

    /* 空链表 */
    if (ptr == NULL)
        return -1;

    i = 2;
    if (pos != 1) {
        while (ptr && i < pos) {
            ptr = ptr->next;
            ++i;
        }
        if (ptr->next == NULL || i > pos)
            return -1;
    }

    if (pos == 1) {
        nextptr = ptr;
        *list = nextptr->next;
    } else {
        nextptr = ptr->next;
        ptr->next = nextptr->next;
    }
    if (item != NULL)
        memcpy(item, &nextptr->data, sizeof(ElemType));
    free(nextptr);

    return 0;
}



/*
 * 不带头结点单链表, 获取第i个位置的元素
 *
 * 获得单链表第 i 个数据的算法思路:
 * 1.声明一个结点 p 指向链表第一个结点，初始化 j 从 1 开始;
 * 2.当 j<i 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，j 累加 1;
 * 3.若到链表末尾 p 为空，则说明第 i 个元素不存在;
 * 4.否则查找成功，返回结点 p 的数据。
 *
 * pos的范围是 [1, length]
 * 成功返回0
 *
 * 时间复杂度为 O(n)
 */
int
get_link_list_item(list_t *list, int pos, ElemType *item)
{
    int i;
    list_t *ptr;

    ptr = list;

    i = 1;
    while (ptr) {
        if (i == pos) {
            memcpy(item, &ptr->data, sizeof(ElemType));
            return 0;
        }
        ptr = ptr->next;
        ++i;
    }

    return -1;
}


/*
 * 不带头结点单链表, 查找元素在表中的位置
 *
 * 返回的位置为[1, length]，若找不到返回0
 *
 * 时间复杂度为 O(n)
 */
int
find_link_list_item(list_t *list, ElemType *item)
{
    int i;
    list_t *ptr;

    ptr = list;

    i = 1;
    while (ptr) {
        if (memcmp(&ptr->data, item, sizeof(ElemType)) == 0)
            return i;
        ptr = ptr->next;
        ++i;
    }

    return 0;
}


/*
 * 不带头结点单链表遍历
 *
 * 时间复杂度为 O(n)
 */
void
trave_link_list(list_t *list, void (*print_info)(int n, ElemType *item))
{
    int i;
    list_t *ptr;

    ptr = list;

    i = 1;
    while (ptr) {
        print_info(i, &ptr->data);
        ptr = ptr->next;
        ++i;
    }

    return;
}


/*
 * 不带头结点单链表整表删除
 *
 * 算法思路如下:
 * 1.声明一结点 p 和q ;
 * 2.将第一个结点赋值给p;
 * 3.循环:
 *   将下一结点赋值给q;
 *   释放p;
 *   将 q 赋值给p
 *
 * 时间复杂度为 O(n)
 */
void
free_link_list(list_t **list)
{
    list_t *ptr, *next;

    ptr = *list;

    while (ptr) {
        next = ptr->next;
        free(ptr);
        ptr = next;
    }

    *list = NULL;

    return;
}




/******************************************************************************/



/*
 * 初始化带头结点的单链表
 *
 * 注意这里是指向指针的指针，因为我们要修改头指针的指向
 */
int
init_list(list_t **list)
{
    list_t *ptr;
    ptr = malloc(sizeof(list_t));
    if (ptr == NULL)
        return -1;

    memset(&ptr->data, 0, sizeof(ElemType));
    ptr->next = NULL;

    *list = ptr; /* 头指针指向头结点 */

    return 0;
}

/*
 * 返回带头结点的单链表节点个数
 *
 * 时间复杂度为 O(n)
 * 如果有个变量跟踪节点个数，则时间复杂度为O(1)
 */
int
get_list_length(list_t *list)
{
    int i;
    list_t *ptr;

    ptr = list;

    i = 0;
    while (ptr->next) {
        ptr = ptr->next;
        ++i;
    }

    return i;
}


/*
 * 判断带头结点的单链表是否为空，为空返回1，否则返回0
 */
int
is_list_empty(list_t *list)
{
    return (list->next == NULL);
}


/*
 * 带头结点单链表插入，如果是空链表，插入第1个节点，否则在第 n 个位置插入新节点
 *
 * 单链表第 n 个数据插入结点的算法思路:
 * 1. 声明一结点 p 指向链表第一个结点，初始化 i 从 1 开始
 * 2. 当 i<n 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，i 累加 1;
 * 3. 若到链表末尾 p 为空，则说明第 n 个元素不存在
 * 4. 否则查找成功，在系统中生成一个空结点 s;
 * 5. 将数据元素 e 赋值给 s->data ;
 * 6. 单链表的插入标准语句 s->next=p->next, p->next=s ;
 * 7. 返回成功。
 *
 * pos的范围是 [1, length+1]
 * 成功返回0
 *
 * 时间复杂度为 O(n)
 */
int
insert_list(list_t **list, int pos, ElemType *item)
{
    int i;
    list_t *ptr;
    list_t *newptr;

    ptr = *list;

    i = 1;

    while (ptr && i < pos) {
        ptr = ptr->next;
        ++i;
    }
    if (ptr == NULL || i > pos)
        return -1;


    newptr = malloc(sizeof(list_t));
    if (newptr == NULL)
        return -2;

    memcpy(&newptr->data, item, sizeof(ElemType));

    newptr->next = ptr->next;
    ptr->next = newptr;


    return 0;
}

int
Insert_LinkList(LinkList *list, int pos, ElemType *item)
{
    int i;
    LinkList ptr;
    LinkList newptr;

    ptr = *list;

    i = 1;

    while (ptr && i < pos) {
        ptr = ptr->next;
        ++i;
    }
    if (ptr == NULL || i > pos)
        return -1;


    newptr = malloc(sizeof(list_t));
    if (newptr == NULL)
        return -2;

    memcpy(&newptr->data, item, sizeof(ElemType));

    newptr->next = ptr->next;
    ptr->next = newptr;

    return 0;
}



/*
 * 带头结点单链表插入 - 头插法
 *
 * 时间复杂度为 O(1)
 */
int
insert_list_head(list_t **list, ElemType *item)
{
    list_t *ptr;
    list_t *newptr;

    ptr = *list;

    newptr = malloc(sizeof(list_t));
    if (newptr == NULL)
        return -1;
    memcpy(&newptr->data, item, sizeof(ElemType));

    newptr->next = ptr->next;
    ptr->next = newptr;

    return 0;
}

/*
 * 带头结点单链表插入 - 尾插法
 *
 * 时间复杂度为 O(n)
 * 如果有指向结尾的指针，则时间复杂度为 O(1)
 */
int
insert_list_tail(list_t **list, ElemType *item)
{
    list_t *ptr;
    list_t *newptr;

    ptr = *list;

    /* point to the tail */
    while (ptr->next)
        ptr = ptr->next;

    newptr = malloc(sizeof(list_t));
    if (newptr == NULL)
        return -1;
    memcpy(&newptr->data, item, sizeof(ElemType));

    newptr->next = NULL;
    ptr->next = newptr;

    return 0;
}



/*
 * 带头结点单链表删除
 *
 * 单链表第 i 个数据删除结点的算法思路:
 * 1.声明一结点 p 指向链表第一个结点， 初始化 j 从1 开始
 * 2.当 j<i 时，就遍历链表， 让 p 的指针向后移动，不断指向下一个结点，j 累加 1
 * 3.若到链表末尾 p 为空，则说明第 i 个元素不存在;
 * 4.否则查找成功，将欲删除的结点 p->next 赋值给q;
 * 5.单链表的删除标准语句 p->next=q->next;
 * 6.将 q 结点中的数据赋值给 e ，作为返回;
 * 7.释放 q 结点;
 * 8.返回成功。
 *
 * pos的范围是 [1, length]
 * 成功返回0
 *
 * 时间复杂度为 O(n)
 */
int
delete_list_item(list_t **list, int pos, ElemType *item)
{
    int i;
    list_t *ptr;
    list_t *nextptr;

    ptr = *list;

    i = 1;
    while (ptr->next && i < pos) {
        ptr = ptr->next;
        ++i;
    }
    if (ptr->next == NULL || i > pos)
        return -1;

    nextptr = ptr->next;
    ptr->next = nextptr->next;

    if (item != NULL)
        memcpy(item, &nextptr->data, sizeof(ElemType));
    free(nextptr);

    return 0;
}



/*
 * 带头结点单链表, 获取第i个位置的元素
 *
 * 获得单链表第 i 个数据的算法思路:
 * 1.声明一个结点 p 指向链表第一个结点，初始化 j 从 1 开始;
 * 2.当 j<i 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，j 累加 1;
 * 3.若到链表末尾 p 为空，则说明第 i 个元素不存在;
 * 4.否则查找成功，返回结点 p 的数据。
 *
 * pos的范围是 [1, length]
 * 成功返回0
 *
 * 时间复杂度为 O(n)
 */
int
get_list_item(list_t *list, int pos, ElemType *item)
{
    int i;
    list_t *ptr;

    ptr = list;

    i = 1;
    while (ptr->next) {
        ptr = ptr->next;
        if (i == pos) {
            memcpy(item, &ptr->data, sizeof(ElemType));
            return 0;
        }
        ++i;
    }

    return -1;
}


/*
 * 带头结点单链表, 查找元素在表中的位置
 *
 * 返回的位置为[1, length]，若找不到返回0
 *
 * 时间复杂度为 O(n)
 */
int
find_list_item(list_t *list, ElemType *item)
{
    int i;
    list_t *ptr;

    ptr = list;

    i = 1;
    while (ptr->next) {
        ptr = ptr->next;
        if (memcmp(&ptr->data, item, sizeof(ElemType)) == 0)
            return i;
        ++i;
    }

    return 0;
}


/*
 * 带头结点单链表遍历
 *
 * 时间复杂度为 O(n)
 */
void
trave_list(list_t *list, void (*print_info)(int n, ElemType *item))
{
    int i;
    list_t *ptr;

    ptr = list;

    i = 1;
    while (ptr->next) {
        ptr = ptr->next;
        print_info(i, &ptr->data);
        ++i;
    }

    return;
}

/*
 * 带头结点单链表整表删除
 *
 * 算法思路如下:
 * 1.声明一结点 p 和q ;
 * 2.将第一个结点赋值给p;
 * 3.循环:
 *   将下一结点赋值给q;
 *   释放p;
 *   将 q 赋值给p
 *
 * 时间复杂度为 O(n)
 */
void
free_list(list_t **list)
{
    list_t *ptr, *next;

    ptr = (*list)->next; /* 指向第一个节点 */

    while (ptr) {
        next = ptr->next;
        free(ptr);
        ptr = next;
    }

    (*list)->next = NULL; /* 头结点指向空 */

    return;
}

